基于遗传算法的片上网络缓冲分配算法

doi:10.13190/jbupt.200906.19.lixh

北京邮电大学学报 ›› 2009, Vol. 32 ›› Issue (6): 19-23.doi: 10.13190/jbupt.200906.19.lixh

基于遗传算法的片上网络缓冲分配算法

李晓辉;曹阳;王力纬;陈晨

(1.武汉大学电子信息学院，武汉 430079；
2.武汉大学软件工程国家重点实验室，武汉 430072)

收稿日期:2009-06-02 修回日期:2009-07-09 出版日期:2009-12-28 发布日期:2009-12-28
通讯作者: 李晓辉

A GA-Based Buffer Allocation Algorithm for Networks-on-Chip Architecture

LI Xiao-hui;CAO Yang;WANG Li-wei;CHEN Chen

(1.School of Electronic Information, Wuhan University, Wuhan 430079, China;
2.State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072,
China)

Received:2009-06-02 Revised:2009-07-09 Online:2009-12-28 Published:2009-12-28
Contact: LI Xiao-Hui

摘要/Abstract

摘要：

针对片上网络有限的缓冲资源，提出了一种缓冲分配算法．该算法首先通过分析模型估算出路由器每个输入通道的负载大小，随后根据输入通道的负载分布情况采用遗传算法来实现缓冲资源的分配. 实验结果表明，在均匀随机流量下，与均匀分配算法和贪婪分配算法相比，新算法能获得更小的网络数据包延时，并可节省约333%的缓冲资源.

关键词: 缓冲分配算法, 遗传算法, 片上网络

Abstract:

For the finite buffer resources in networks-on-chip, a buffer allocation algorithm is proposed. The proposed algorithm first estimates the load on each input channel in different routers across the chip by the performance analytical model. Then, it uses genetic algorithm to allocate the resources according to the distribution of the load on all the channels. Simulation results indicate that, under uniform traffic, this algorithm can get less average packet latency than those by uniform allocation and greedy allocation strategy. At the same time, about 33.3% buffer can be saved.

Key words: buffer allocation algorithm, genetic algorithm, networks-on-chip

中图分类号:

TP301

李晓辉;曹阳;王力纬;陈晨. 基于遗传算法的片上网络缓冲分配算法[J]. 北京邮电大学学报, 2009, 32(6): 19-23.

LI Xiao-hui;CAO Yang;WANG Li-wei;CHEN Chen. A GA-Based Buffer Allocation Algorithm for Networks-on-Chip Architecture[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(6): 19-23.

参考文献

[1] Henkel J, Wolf W, Chakradhar S. On-chip networks: a scalable, communication centric embedded system design paradigm[C] // Proceedings of the IEEE International Conference on VLSI Design (VLSI Design 2008). Mumbai: IEEE Press, 2004: 845-851.
[2] Hu Jingcao, Ogras U Y, Marculescu R. System- level buffer allocation for application specific networks-on-chip router design[J]. IEEE Transaction on Computer-aided Design of Integrated Circuits and Systems, 2006, 25(12): 2919-2933.
[3] 王力纬, 曹阳, 李晓辉, 等. 虫孔路由NOC的缓冲分配算法[J]. 北京邮电大学学报, 2008, 31(4):29-32.
Wang Liwei, Cao Yang, Li Xiaohui, et al. A buffer allocation algorithm for wormhole routing networks-on-chip[J]. Journal of Beijing University of Posts and Telecommunications, 2008, 31(4): 29-32.
[4] Barati H, Movaghar A, Barati A, et al. Routing algorithms study and comparing in interconnection networks[C] // Proceedings of 3rd International Conference on Information and Communication Technologies (ICICT 2008). Damascus: IEEE Press, 2008:1-5.
[5] Bahn J H, Bagherzadeh N. Design of simulation and analytical models for a 2d-meshed asymmetric adaptive router[J]. IET Computer Digital Technology, 2008, 2(1): 63-73.
[6] Patooghy A, Sarbazi-azad H. Analytical performance modeling of partially adaptive routing in wormhole hypercube[C] // Proceedings of 20th International Parallel and Distributed Processing Symposium (IPDPS 2006). Rhodes Island: IEEE Press, 2006:1-7.
[7] Duato J, Yalamanchili S, Lionel M. Interconnection networks-an engineering approach[M]. San Francisco: Morgan Kaufmann Publisher, 2003.
[8] Hu Jingcao, Marculescu R. DyAD-smart routing for networks-on-chip[C] // Proceedings of the 41st Design Automatic Conference (DAC 2004). San Diego: ACM Press, 2004: 260-263.

[1]	许同乐, 苏元浩, 孟良, 兰孝升, 李云凤. 优化GAN的风电机组齿轮箱故障诊断方法[J]. 北京邮电大学学报, 2023, 46(3): 62-66.
[2]	张经天, 马莹, 翁迅, 孙壮志, 张继龙. 四向穿梭车系统的提升机调度优化[J]. 北京邮电大学学报, 2022, 45(1): 19-25,81.
[3]	余修武, 黄露平, 刘永, 余昊, 李佩. 遗传-禁忌搜索优化的三维DV-Hop定位算法[J]. 北京邮电大学学报, 2021, 44(4): 75-81.
[4]	王怀江, 刘晓平, 王刚, 韩松. 基于改进遗传算法的移动机械臂拣选路径优化[J]. 北京邮电大学学报, 2020, 43(5): 34-40.
[5]	刘寒. 混合采样与遗传算法相结合的垃圾网页检测[J]. 北京邮电大学学报, 2019, 42(6): 111-117.
[6]	赵雄文, 孙宁姚, 耿绥燕, 张钰, 杜飞. 基于最小二乘支持向量机的时变信道建模[J]. 北京邮电大学学报, 2019, 42(5): 29-35.
[7]	徐涵喆, 黄逸彬, 杨赫, 周钟秉, 刘晓. 基于规则的城市地下车库外圈车位排布启发式算法[J]. 北京邮电大学学报, 2019, 42(4): 102-108.
[8]	舒坚, 贾晨浩, 陶娟. 基于改进最小二乘支持向量回归机的链路质量预测[J]. 北京邮电大学学报, 2018, 41(2): 44-49.
[9]	张洪, 龚勇, 潘志松, 胡谷雨. 结合遗传算法与启发式搜索的卫星频谱资源动态规划[J]. 北京邮电大学学报, 2017, 40(s1): 5-9.
[10]	蔚承英, 吴兰, 刘焕淋, 陈勇. 编码链路最少的多源光组播路由[J]. 北京邮电大学学报, 2017, 40(5): 87-91.
[11]	山蕊, 沈绪榜, 蒋林, 朱筠, 宋辉. 面向阵列处理器的分布式共享存储结构设计[J]. 北京邮电大学学报, 2017, 40(4): 9-15.
[12]	李鹏, 刘远, 王裕华. 基于NSGA-II的通信电缆绞合节距优化[J]. 北京邮电大学学报, 2017, 40(2): 88-92.
[13]	吴润泽, 高丽媛, 唐良瑞, 朱佳佳. 认知无线网Underlay模式下频谱资源优化分配[J]. 北京邮电大学学报, 2017, 40(1): 105-110.
[14]	冯霞, 郝慧敏. GA-ACO算法用于IMX系统测试数据自动生成[J]. 北京邮电大学学报, 2016, 39(5): 99-103.
[15]	孙学宏, 于向明, 刘丽萍, 曾志民, 张成. 一种新的INSAR相位解缠方法[J]. 北京邮电大学学报, 2016, 39(2): 10-14,34.

基于遗传算法的片上网络缓冲分配算法

A GA-Based Buffer Allocation Algorithm for Networks-on-Chip Architecture

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价